package training;

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_7_18_Training {
    //删除元素后和的最小差值
    public long minimumDifference(int[] nums) {
        int len = nums.length;
        int n=len/3;
        //最大堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        long[] ansF =new long[n+1];//表示第一个数组以n+i结尾的和(最小);
        long sumF=0;
        for(int i=0;i<2*n;++i){
            if(i>=n){
                sumF+=nums[i];
                heap.offer(nums[i]);
                sumF-=heap.poll();
                ansF[i-n+1]=sumF;
            }else{
                sumF+=nums[i];
                heap.offer(nums[i]);
                if(i==n-1) ansF[0]=sumF;
            }
        }
        long[] ansS=new long[n+1];//表示第二个数组以n+i开始的和(最大);
        heap = new PriorityQueue<>();
        long sumS=0;
        for(int i=len-1;i>=n;--i){
            if(i<2*n){
                sumS+=nums[i];
                heap.offer(nums[i]);
                sumS-=heap.poll();
                ansS[2*n-i]=sumS;
            }else{
                sumS+=nums[i];
                heap.offer(nums[i]);
                if(i==2*n) ansS[0]=sumS;
            }
        }
        long max=100000000001L;
        for(int i=0;i<=n;++i){
            max=Math.min(max,ansF[i]-ansS[n-i]);
        }
        return max;
    }
}
